package main.图;

import java.util.ArrayList;
import java.util.List;

/**
 * @author tmh
 * @date 2024/7/25 14:56
 * @description
 */
public class T207课程表 {
    public boolean canFinish(int numCourses, int[][] prerequisites) {
        //创建一个邻接表来表示课程图
        List<List<Integer>> courseGraph = new ArrayList<>();
        for (int i = 0; i < numCourses; i++) {
            courseGraph.add(new ArrayList<>());
        }
        //填充图的邻接表
        for (int[] prerequisite : prerequisites) {
            courseGraph.get(prerequisite[1]).add(prerequisite[0]);
        }
        //创建一个标记数组来追踪每个节点的访问状态
        int[] visited = new int[numCourses];
        //对每个课程进行dfs
        for (int i = 0; i < numCourses; i++) {
            if (!dfs(courseGraph,visited,i)){
                return false;
            }
        }
        return true;
    }

    private boolean dfs(List<List<Integer>> graph, int[] visited, int course) {
        //说明有环，返回false  (访问中的节点再次被访问，说明有环)
        if (visited[course] == 1) {
            return false;
        }
        //如果该节点访问过，就返回true
        if (visited[course] == 2) {
            return true;
        }
        //把当前节点标记为访问中
        visited[course] = 1;

        //对当前课程后续的所有课程进行dfs
        for (Integer nextCourse : graph.get(course)) {
            if (!dfs(graph, visited, nextCourse)) {
                return false;
            }
        }
        //把当前节点标记为已经访问过
        visited[course]=2;
        return true;
    }
}
